The present invention relates to a method for speeding up modular exponentiation for a fixed base element in a public-key cryptosystem, and more particularly, to an exponentiation method using a fixed base element-dependent pre-computation table.
Since Diffie and Hellman introduced the concept of a public-key cryptosystem in 1976, many cryptographic protocols have been developed based on the public-key cryptographic method. A public-key cryptosystem utilizes the property that it is computationally infeasible to derive a matching secret key from the public key even if the public key is made public, as long as the underlying mathematical problem remains intractable.
Two typical examples of such mathematical problems are the discrete logarithm problem and the integer factorization problem. However, the cryptosystem designed based on these problems gives a relatively poor performance compared to a conventional or symmetric cryptosystem. Therefore, the development of algorithms for reducing the amount of computation has been one of the important research fields in modern cryptology.
The most frequently used operation required in a public key cryptosystem is an exponentiation in a finite group. Typical groups include a multiplicative group in an integer ring or finite field, and an additive group on points of an elliptic curve defined in a finite field. In general, exponentiation implies computing X.sup.R for two random elements X and R in a given group. However, in many cryptographic protocols it is often necessary to compute g.sup.R for a random exponent R and a fixed base element g. For example, many protocols have been developed for authentication and digital signatures based on the difficulty of solving the discrete logarithm problem.
The problem of speeding up exponentiation in a given group (usually Z.sub.N, where N is a large prime number or the product of two large prime numbers) is very important for the efficient implementation of most public-key cryptosystems. Hereinafter, for the sake of convenience, it is assumed that the computation is performed over Z.sub.N, and thus multiplication denotes multiplication mod N. However, the method proposed in the present invention can be adapted for any group. Throughout the following explanation, g will be used as a fixed element in Z.sub.N and R represents an n-bit random exponent over [0, 2.sup.n), .vertline.S.vertline. denotes the bit-length of S for an integer S or the cardinality of S for a set S, .left brkt-top.x.right brkt-top. denotes the smallest integer not less than x (e.g., .left brkt-top.1.29.right brkt-top.=2), and .left brkt-bot.x.right brkt-bot. denotes the greatest integer not greater than x (e.g., .left brkt-bot.1.29.right brkt-bot.=1).
A typical method for exponentiation is to use the binary algorithm, also known as the square-and-multiply method. For a 512-bit modulus and exponent, this method requires 766 multiplications on average and 1022 in the worst case. The signed binary algorithm can reduce the required number of multiplications to around 682 on average and 768 in the worst case.
On the other hand, using a moderate storage capacity for intermediate values, the performance can be considerably improved. For example, Knuth's five-window algorithm (see "The Art of Computer Programming," Vol. 2, Seminumerical Algorithm, by D. E. Knuth, 1981) performs exponentiation in about 609 multiplications on average, including the on-line pre-computation operation of sixteen multiplications.
The fastest algorithm known for exponentiation is the windowing method based on addition chains, where bigger windows, for example, ten in size, are used and more storage capacity for intermediate values are needed. Though finding the shortest addition chain is an NP-complete problem, it is reported that, by applying heuristics, an addition chain having a length of around 605 can be computed.
These general methods can be used for any cryptosystem requiring exponentiation such as the RSA (see "A Method for Obtaining Digital Signatures and Public-key Cryptosystems," in Communications ACM, by R. L. Rivest, A. Shamir and L. Adleman, 21(2), pp 126, 1978) and El Gamal (see "A Public Key Cryptosystem and a Signature Scheme Based on the Discrete Logarithm," in IEEE Transactions on Information Theory, by T. El Gamal, 31(4), pp 472, 1985) systems. However, in many cryptographic protocols based on the discrete logarithm problem, it is necessary to compute g.sup.R for a fixed base g but for a randomly chosen exponent R. Therefore, one can construct a pre-computation table depending only on the fixed base g, which can then be used to speed up the evaluation of g.sup.R for any random exponent R. As will be seen later, such pre-computation technique will substantially reduce the number of multiplications required for exponentiation.